package algorithm.easy;

public class Solution112 {
    //输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    //输出：true
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null && targetSum!=0){
            return false;
        }
        if(targetSum - root.val ==0){
            return true;
        }
        boolean leftFlag = false;
        boolean rightFlag = false;
        if(root.left !=null){
            leftFlag = hasPathSum(root.left,targetSum-root.val);
        }
        if(root.right !=null){
            rightFlag = hasPathSum(root.right,targetSum-root.val);
        }


        return leftFlag ||  rightFlag;

    }

    public static void main(String[] args){
        TreeNode treeNode = TreeNode.init112();
        int targetSum = 22;
        System.out.println(hasPathSum(treeNode,targetSum));
    }
}
